# LeetCode 518、零钱兑换II
# 一、题目描述
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
提示：
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的所有值 互不相同0 <= amount <= 5000
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 零钱兑换II（LeetCode 518）：https://leetcode.cn/problems/coin-change-2/submissions/
class Solution {
public int change(int amount, int[] coins) {
// 经典的完全背包问题
// 二维数组：状态定义:dp[i][j]表示从数组 coins 中前 i 个硬币中选择得到价值为 j 的硬币组合数
int[][] dp = new int[coins.length + 1][ amount + 1 ];
// 只有当不选取任何硬币时，金额之和才为 0，此时只有 1 种硬币组合
dp[0][0] = 1;
// Tips：前 i 个物品表示的是编号从 [ 0 , i - 1] 这些物品，即最后一个物品编号为 i - 1
// coins 数组的大小就是硬币的个数
for( int i = 1 ; i <= coins.length ; i++){
// 遍历背包容量
for( int j = 0 ; j <= amount ; j++){
// 背包容量小于当前硬币的值，即背包容量已经不足以拿第 i 个硬币了
// 第 i 个硬币即下标为 i - 1 的那个硬币
if( j < coins[i - 1]){
// 硬币组合数就是去考虑当前背包容量情况下，从前 i - 1 个物品中选择出的硬币组合数
dp[i][j] = dp[i - 1][j];
// 背包容量足够拿第 i 个物品，那么可拿也可不拿
// 1、拿了，那么硬币组合数是前 i 个硬币扣除第 i 个硬币的情况下的硬币组合数
// 2、不拿，那么就是从前 i - 1 个硬币中选择出的硬币组合数
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
}
// System.out.print(dp[i][j] + "");
}
// System.out.println();
}
return dp[coins.length][amount];
}
}
# 一维****DP
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 零钱兑换II（LeetCode 518）：https://leetcode.cn/problems/coin-change-2/submissions/
class Solution {
public int change(int amount, int[] coins) {
// 经典的完全背包问题
// 二维数组：状态定义:dp[i][j]表示从数组 coins 中前 i 个硬币中选择得到价值为 j 的硬币组合数
int[] dp = new int[ amount + 1 ];
// 只有当不选取任何硬币时，金额之和才为 0，此时只有 1 种硬币组合
dp[0] = 1;
// Tips：前 i 个物品表示的是编号从 [ 0 , i - 1] 这些物品，即最后一个物品编号为 i - 1
// coins 数组的大小就是硬币的个数
for( int i = 1 ; i <= coins.length ; i++){
// 遍历背包容量
for( int j = 0 ; j <= amount ; j++){
// 背包容量足够拿第 i 个物品，那么可拿也可不拿
// 1、拿了，那么硬币组合数是前 i 个硬币扣除第 i 个硬币的情况下的硬币组合数
// 2、不拿，那么就是从前 i - 1 个硬币中选择出的硬币组合数
if( j >= coins[i - 1]){
// 硬币组合数就是去考虑当前背包容量情况下，从前 i - 1 个物品中选择出的硬币组合数
dp[j] = dp[j] + dp[j-coins[i-1]];
}
}
}
return dp[amount];
}
}
# **2、**C++ 代码
class Solution {
public:
int change(int amount, vector<int>& coins) {
// 经典的完全背包问题
// 二维数组：状态定义:dp[i][j]表示从数组 coins 中前 i 个硬币中选择得到价值为 j 的硬币组合数
int n = coins.size();
vector<vector<int>>dp(n + 1, vector<int>(amount + 1 , 0));
// 只有当不选取任何硬币时，金额之和才为 0，此时只有 1 种硬币组合
dp[0][0] = 1;
// Tips：前 i 个物品表示的是编号从 [ 0 , i - 1] 这些物品，即最后一个物品编号为 i - 1
// coins 数组的大小就是硬币的个数
for( int i = 1 ; i <= n ; i++){
// 遍历背包容量
for( int j = 0 ; j <= amount ; j++){
// 背包容量小于当前硬币的值，即背包容量已经不足以拿第 i 个硬币了
// 第 i 个硬币即下标为 i - 1 的那个硬币
if( j < coins[i - 1]){
// 硬币组合数就是去考虑当前背包容量情况下，从前 i - 1 个物品中选择出的硬币组合数
dp[i][j] = dp[i - 1][j];
// 背包容量足够拿第 i 个物品，那么可拿也可不拿
// 1、拿了，那么硬币组合数是前 i 个硬币扣除第 i 个硬币的情况下的硬币组合数
// 2、不拿，那么就是从前 i - 1 个硬币中选择出的硬币组合数
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
}
}
}
return dp[n][amount];
}
};
# 3、Python 代码
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n = len(coins)
dp = [[0]*(amount+1) for _ in range(n+1)]
# 初始化
dp[0][0] = 1
# 完全背包
# 第一层循环：遍历硬币
for i in range(1, n+1):
# 第二层循环：遍历背包
for j in range(amount+1):
# 容量有限，无法选择第i个硬币
if j < coins[i-1]:
dp[i][j] = dp[i-1][j]
# 可选择第i个硬币
else:
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
return dp[n][amount]